1. Field of the Invention
The invention generally relates to state machines and in particular to a programmable state machine for use within the integrated circuits and the like.
2. Description of the Related Art
State machines are commonly employed in computer and electrical systems for storing information representing the state of a system and for outputting a new state based upon the current state and any input signals received. For example, within computer systems, state machines are often employed in connection with bus systems where the state machine facilitates communication over the bus, particularly by coordinating "hand-shaking" protocols and the like. State machines, however, are also employed in such diverse systems as traffic lights, elevators, etc.
FIG. 1 illustrates a generalized six-state system wherein a transition may occur from each individual state back to itself and to every other state. Accordingly, a total of 36 transitions are possible. In general, for a system having N states, a total of N.sup.2 transitions are possible.
Conventionally, combinatorial logic is employed to implement the state machine. The combinatorial logic is configured to output a new state value based upon the current state and any input signals received.
A disadvantage of employing combinatorial logic to represent a state machine is that the state machine, once designed and fabricated, cannot be changed. Hence, if any states are added or removed or any state transitions are changed, a new state machine must be designed and fabricated employing different combinatorial logic. This is particularly a problem in computer system technology which may be need to be upgraded frequently to accommodate new peripheral systems. For example, state machines implementing bus protocols may need to be modified to accommodate new bus protocols.
Accordingly, it would be desirable to provide a programmable state machine which can be programmed, and subsequently reprogrammed, to represent any of a variety of possible systems. With a programmable state machine, if the system represented by the state machine changes, the state machine is merely reprogrammed to account for the changes, without requiring redesign and refabrication of any combinatorial logic circuitry.
One proposed implementation for a programmable state machine, illustrated in FIG. 2, employs random access memory (RAM) to represent the overall system. More specifically, FIG. 2 illustrates a state machine 10 having a RAM 12 and an address selection unit 14. The address selection unit receives input signals and signals representing the current state of the system and, based upon that information, determines the address of an entry within RAM 12 storing the corresponding new state.
FIG. 3 illustrates RAM 12 in greater detail. RAM 12 has one column of storage locations for each current state of the system and one element, within each column, for every possible new state into which the system may transition based upon the current state and the input signals. Hence, for a system having N states, the RAM maintains N.sup.2 entries. In use, the address selection unit determines the address of the new state then controls the RAM to output the new state. The overall state machine may be reprogrammed by modifying the contents of RAM 12.
Although the RAM programmable state machine of FIGS. 2 and 3 provides the flexibility of reprogramming for any possible new system (having up to a maximum predetermined number of states N), such is achieved at the expense of requiring considerable memory space. For example, if N is large, e.g., 64, 128 or 256, the amount of memory space required may become prohibitive or unduly expensive. As a more specific example, if the programmable state machine is intended to allow up to 64 states and to test up to 6 independent input conditions simultaneously, the RAM must be capable of storing 4096 entries. If 6 possible independent outputs are required, the RAM must store 12 bits per entry, for a total size of 6144 bytes. Such may be prohibitively large, particularly if the state machine is intended only as one single component of a complex micro-controller or microprocessor.
The large amount of memory is required, in part, because the programmable RAM state machine is configured to account for every possible transition between every possible state. In practical systems, however, only a fraction of the total number of possible transitions can actually occur. In other words, practical systems do not typically conform to the generalized state diagram of FIG. 1. FIG. 4 illustrates a practical system, a 3-bit counter, which includes 8 states representing numbers 0-7. In the system of FIG. 4, only two general types of transitions occur. Either the system transitions to a next higher state as part of a normal count or the system transitions back to the default state of 000 in response to a reset signal. Hence, only a total of 16 transitions are permissible, rather than the 64 transitions theoretically possible.
Hence, if represented using the RAM programmable state machine of FIGS. 2 and 3, the system of FIG. 4 would require a 64 entry RAM wherein most of the entries are empty because the corresponding transition cannot occur. Moreover, many of the entries will be repeated or redundant. For example, all transitions occurring as a result of a reset input signal specify the same state "000".
It would be desirable to provide an improved programmable state machine which requires less memory space than a RAM-programmable state machine for use with practical systems which do not involve the maximum number of possible transitions and which more efficiently accounts for any redundant states, such as those occurring following reception of a reset signal. It is to these ends and aspects of the present invention are drawn.